/**
 * 
 */
package org.swing.utility.common.collection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;

import org.apache.commons.collections15.set.ListOrderedSet;
import org.apache.commons.lang.NotImplementedException;
import org.swing.utility.common.map.MapValueComparator;

/**
 * @author lqnhu
 *
 */
public abstract class CollectionUtil {
	private static final Random RANDOM = new Random();

	public static <T extends Comparable<T>> List<T> sort(List<T> list) {
		Collections.sort(list);
		return (list);
	}

	public static <T extends Comparable<T>> Collection<T> sort(
			Collection<T> items) {
		List<T> list = new ArrayList<T>(items);
		Collections.sort(list);
		return (list);
	}

	/**
	 * Put all of the elements in items into the given array This assumes that
	 * the array has been pre-allocated
	 *
	 * @param <T>
	 * @param items
	 * @param array
	 */
	public static <T> void toArray(Collection<T> items, Object array[],
			boolean convert_to_primitive) {
		assert (items.size() == array.length);
		int i = 0;
		for (T t : items) {
			if (convert_to_primitive) {
				if (t instanceof Long) {
					array[i] = ((Long) t).longValue();
				} else if (t instanceof Integer) {
					array[i] = ((Integer) t).intValue();
				} else if (t instanceof Double) {
					array[i] = ((Double) t).doubleValue();
				} else if (t instanceof Boolean) {
					array[i] = ((Boolean) t).booleanValue();
				}
			} else {
				array[i] = t;
			}
		}
		return;
	}

	/**
	 * Convert a Collection of Numbers to an array of primitive ints Null values
	 * will be skipped in the array
	 * 
	 * @param items
	 * @return
	 */
	public static int[] toIntArray(Collection<? extends Number> items) {
		int ret[] = new int[items.size()];
		int idx = 0;
		for (Number n : items) {
			if (n != null)
				ret[idx] = n.intValue();
			idx += 1;
		} // FOR
		return (ret);
	}

	/**
	 * Convert a Collection of Numbers to an array of primitive longs Null
	 * values will be skipped in the array
	 * 
	 * @param items
	 * @return
	 */
	public static long[] toLongArray(Collection<? extends Number> items) {
		long ret[] = new long[items.size()];
		int idx = 0;
		for (Number n : items) {
			if (n != null)
				ret[idx] = n.longValue();
			idx += 1;
		} // FOR
		return (ret);
	}

	/**
	 * Convert a Collection of Numbers to an array of primitive doubles Null
	 * values will be skipped in the array
	 * 
	 * @param items
	 * @return
	 */
	public static double[] toDoubleArray(Collection<? extends Number> items) {
		double ret[] = new double[items.size()];
		int idx = 0;
		for (Number n : items) {
			if (n != null)
				ret[idx] = n.doubleValue();
			idx += 1;
		} // FOR
		return (ret);
	}

	/**
	 * Put all the values of an Iterator into a List
	 *
	 * @param <T>
	 * @param it
	 * @return
	 */
	public static <T> List<T> list(Iterator<T> it) {
		List<T> list = new ArrayList<T>();
		CollectionUtil.addAll(list, it);
		return (list);
	}

	/**
	 * Put all of the values of an Enumeration into a new List
	 *
	 * @param <T>
	 * @param e
	 * @return
	 */
	public static <T> List<T> list(Enumeration<T> e) {
		return (list(iterable(e)));
	}

	/**
	 * Put all of the values of an Iterable into a new List
	 *
	 * @param <T>
	 * @param it
	 * @return
	 */
	public static <T> List<T> list(Iterable<T> it) {
		return (list(it.iterator()));
	}

	/**
	 * Put all the values of an Iterator into a Set
	 *
	 * @param <T>
	 * @param it
	 * @return
	 */
	public static <T> Set<T> set(Iterator<T> it) {
		Set<T> set = new HashSet<T>();
		CollectionUtil.addAll(set, it);
		return (set);
	}

	/**
	 * Put all of the values of an Iterable into a new Set
	 *
	 * @param <T>
	 * @param it
	 * @return
	 */
	public static <T> Set<T> set(Iterable<T> it) {
		return (set(it.iterator()));
	}

	/**
	 * Returns a list containing the string representations of the elements in
	 * the collection
	 *
	 * @param <T>
	 * @param data
	 * @return
	 */
	public static <T> List<String> toStringList(Collection<T> data) {
		List<String> ret = new ArrayList<String>();
		for (T t : data)
			ret.add(t.toString());
		return (ret);
	}

	/**
	 * Returns a set containing the string representations of the elements in
	 * the collection
	 *
	 * @param <T>
	 * @param data
	 * @return
	 */
	public static <T> Set<String> toStringSet(Collection<T> data) {
		Set<String> ret = new HashSet<String>();
		for (T t : data)
			ret.add(t.toString());
		return (ret);
	}

	/**
	 * Return a random value from the given Collection
	 *
	 * @param <T>
	 * @param items
	 */
	public static <T> T random(Collection<T> items) {
		return (CollectionUtil.random(items, RANDOM));
	}

	/**
	 * Return a random value from the given Collection
	 *
	 * @param <T>
	 * @param items
	 * @param rand
	 * @return
	 */
	public static <T> T random(Collection<T> items, Random rand) {
		int idx = rand.nextInt(items.size());
		return (CollectionUtil.get(items, idx));
	}

	/**
	 * Return a random value from the given Iterable
	 *
	 * @param <T>
	 * @param it
	 * @return
	 */
	public static <T> T random(Iterable<T> it) {
		return (CollectionUtil.random(it, RANDOM));
	}

	/**
	 * Return a random value from the given Iterable
	 *
	 * @param <T>
	 * @param it
	 * @param rand
	 * @return
	 */
	public static <T> T random(Iterable<T> it, Random rand) {
		List<T> list = new ArrayList<T>();
		for (T t : it) {
			list.add(t);
		} // FOR
		return (CollectionUtil.random(list, rand));
	}

	@SuppressWarnings("unchecked")
	public static <E extends Enum<?>> Set<E> getAllExcluding(E elements[],
			E... excluding) {
		Set<E> exclude_set = new HashSet<E>();
		for (E e : excluding)
			exclude_set.add(e);
		Set<E> elements_set = new HashSet<E>();
		for (int i = 0; i < elements.length; i++) {
			if (!exclude_set.contains(elements[i]))
				elements_set.add(elements[i]);
		} // FOR
		return (elements_set);
		// Crappy java....
		// Object new_elements[] = new Object[elements_set.size()];
		// elements_set.toArray(new_elements);
		// return ((E[])new_elements);
	}

	/**
	 * Add all the items in the array to a Collection
	 *
	 * @param <T>
	 * @param data
	 * @param items
	 */
	@SuppressWarnings("unchecked")
	public static <T> Collection<T> addAll(Collection<T> data, T... items) {
		for (T i : (T[]) items) {
			data.add(i);
		}
		return (data);
	}

	/**
	 * Add all the items in the Enumeration into a Collection
	 *
	 * @param <T>
	 * @param data
	 * @param items
	 */
	public static <T> Collection<T> addAll(Collection<T> data,
			Enumeration<T> items) {
		while (items.hasMoreElements()) {
			data.add(items.nextElement());
		} // WHILE
		return (data);
	}

	/**
	 * Add all of the items from the Iterable into the given collection
	 *
	 * @param <T>
	 * @param data
	 * @param items
	 */
	public static <T> Collection<T> addAll(Collection<T> data, Iterable<T> items) {
		return (CollectionUtil.addAll(data, items.iterator()));
	}

	/**
	 * Add all of the items from the Iterator into the given collection
	 *
	 * @param <T>
	 * @param data
	 * @param items
	 */
	public static <T> Collection<T> addAll(Collection<T> data, Iterator<T> items) {
		while (items.hasNext()) {
			data.add(items.next());
		} // WHILE
		return (data);
	}

	/**
	 * @param <T>
	 * @param <U>
	 * @param map
	 * @return
	 */
	public static <T, U extends Comparable<U>> T getGreatest(Map<T, U> map) {
		T max_key = null;
		U max_value = null;
		for (T key : map.keySet()) {
			U value = map.get(key);
			if (max_value == null || value.compareTo(max_value) > 0) {
				max_value = value;
				max_key = key;
			}
		} // FOR
		return (max_key);
	}

	/**
	 * Return the first item in a Iterable
	 *
	 * @param <T>
	 * @param items
	 * @return
	 */
	public static <T> T first(Iterable<T> items) {
		return (CollectionUtil.get(items, 0));
	}

	/**
	 * Return the first item in a Iterator
	 *
	 * @param <T>
	 * @param items
	 * @return
	 */
	public static <T> T first(Iterator<T> items) {
		return (items.hasNext() ? items.next() : null);
	}

	/**
	 * Returns the first item in an Enumeration
	 *
	 * @param <T>
	 * @param items
	 * @return
	 */
	public static <T> T first(Enumeration<T> items) {
		return (items.hasMoreElements() ? items.nextElement() : null);
	}

	/**
	 * Return the ith element of a set. Super lame
	 *
	 * @param <T>
	 * @param items
	 * @param idx
	 * @return
	 */
	public static <T> T get(Iterable<T> items, int idx) {
		if (items == null) {
			return (null);
		} else if (items instanceof List<?>) {
			return ((List<T>) items).get(idx);
		} else if (items instanceof ListOrderedSet<?>) {
			return ((ListOrderedSet<T>) items).get(idx);
		} else if (items instanceof SortedSet<?> && idx == 0) {
			SortedSet<T> set = (SortedSet<T>) items;
			return (set.isEmpty() ? null : set.first());
		}
		int ctr = 0;
		for (T t : items) {
			if (ctr++ == idx)
				return (t);
		}
		return (null);
	}

	/**
	 * Return the last item in an Iterable
	 *
	 * @param <T>
	 * @param items
	 * @return
	 */
	public static <T> T last(Iterable<T> items) {
		T last = null;
		if (items instanceof List<?>) {
			List<T> list = (List<T>) items;
			last = (list.isEmpty() ? null : list.get(list.size() - 1));
		} else if (items instanceof SortedSet<?>) {
			SortedSet<T> set = (SortedSet<T>) items;
			last = (set.isEmpty() ? null : set.last());
		} else {
			for (T t : items) {
				last = t;
			}
		}
		return (last);
	}

	/**
	 * Return the last item in an array
	 *
	 * @param <T>
	 * @param items
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public static <T> T last(T... items) {
		if (items != null && items.length > 0) {
			return (items[items.length - 1]);
		}
		return (null);
	}

	/**
	 * Return a new map sorted by the values of the given original map
	 *
	 * @param <K>
	 * @param <V>
	 * @param map
	 * @return
	 */
	public static <K, V extends Comparable<V>> Map<K, V> sortByValues(
			Map<K, V> map) {
		return sortByValues(map, false);
	}

	/**
	 * @param <K>
	 * @param <V>
	 * @param map
	 * @param reverse
	 * @return
	 */
	public static <K, V extends Comparable<V>> Map<K, V> sortByValues(
			Map<K, V> map, boolean reverse) {
		SortedMap<K, V> sorted = new TreeMap<K, V>(
				new MapValueComparator<K, V>(map, reverse));
		sorted.putAll(map);
		return (sorted);
	}

	// public static <K, V extends Comparable<? super V>> List<K>
	// getKeysSortedByValue(Map<K, V> map) {
	// final int size = map.size();
	// final List<K> keys = new ArrayList<K>(size);
	// if (true || size == 1) {
	// keys.addAll(map.keySet());
	// } else {
	// final List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>(size);
	// list.addAll(map.entrySet());
	// final ValueComparator<V> cmp = new ValueComparator<V>();
	// Collections.sort(list, cmp);
	// for (int i = 0; i < size; i++) {
	// keys.set(i, list.get(i).getKey());
	// }
	// }
	// return keys;
	// }
	//
	// private static final class ValueComparator<V extends Comparable<? super
	// V>> implements Comparator<Map.Entry<?, V>> {
	// public int compare(Map.Entry<?, V> o1, Map.Entry<?, V> o2) {
	// return o1.getValue().compareTo(o2.getValue());
	// }
	// }
	/**
	 * @param <K>
	 * @param <V>
	 * @param map
	 * @return
	 */
	public static <K extends Comparable<?>, V> List<V> getSortedList(
			SortedMap<K, Collection<V>> map) {
		List<V> ret = new ArrayList<V>();
		for (K key : map.keySet()) {
			ret.addAll(map.get(key));
		} // FOR
		return (ret);
	}

	/**
	 * Wrap an Iterable around an Iterator
	 *
	 * @param <T>
	 * @param it
	 * @return
	 */
	public static <T> Iterable<T> iterable(final Iterator<T> it) {
		return (new Iterable<T>() {

			public Iterator<T> iterator() {
				return (it);
			}
		});
	}

	public static <T> Iterable<T> iterable(final T values[]) {
		return (new Iterable<T>() {

			public Iterator<T> iterator() {
				return new Iterator<T>() {
					private int idx = 0;

					public boolean hasNext() {
						return (this.idx < values.length);
					}

					public T next() {
						return (values[this.idx++]);
					}

					public void remove() {
						throw new NotImplementedException();
					}
				};
			}
		});
	}

	/**
	 * Wrap an Iterable around an Enumeration
	 * 
	 * @param <T>
	 * @param e
	 * @return
	 */
	public static <T> Iterable<T> iterable(final Enumeration<T> e) {
		return (new Iterable<T>() {

			public Iterator<T> iterator() {
				return new Iterator<T>() {

					public boolean hasNext() {
						return (e.hasMoreElements());
					}

					public T next() {
						return (e.nextElement());
					}

					public void remove() {
						throw new NotImplementedException();
					}
				};
			}
		});
	}

	/**
	 * Wrap an Iterable around an Enumeration that is automatically cast to the
	 * specified type
	 * 
	 * @param <T>
	 * @param e
	 * @return
	 */
	public static <T> Iterable<T> iterable(final Enumeration<?> e,
			Class<T> castType) {
		return (new Iterable<T>() {

			public Iterator<T> iterator() {
				return new Iterator<T>() {

					public boolean hasNext() {
						return (e.hasMoreElements());
					}

					@SuppressWarnings("unchecked")
					public T next() {
						return ((T) e.nextElement());
					}

					public void remove() {
						throw new NotImplementedException();
					}
				};
			}
		});
	}

	public static <T> T pop(Collection<T> items) {
		T t = CollectionUtil.first(items);
		if (t != null) {
			boolean ret = items.remove(t);
			assert (ret);
		}
		return (t);
	}

	/**
	 * Return an ordered array of the hash codes for the given items Any null
	 * item will have a null hash code
	 */
	public static int[] hashCode(Iterable<?> items) {
		List<Integer> codes = new ArrayList<Integer>();
		for (Object o : items) {
			codes.add(o != null ? o.hashCode() : null);
		}
		return CollectionUtil.toIntArray(codes);
	}

	/**
	 * Simple case-insensitive lexical comparator of objects using their
	 * {@link Object#toString()} value.
	 */
	final public static Comparator<Object> OBJECT_TOSTRING_COMPARATOR = new Comparator<Object>() {
		public int compare(final Object o1, final Object o2) {
			return o1.toString().compareToIgnoreCase(o2.toString());
		}
	};

	public static <T> List<T> makeList(final T... list) {
		final List<T> result = new ArrayList<T>();
		Collections.addAll(result, list);
		return result;
	}

	public static <T> Set<T> makeSet(final T... list) {
		final Set<T> result = new HashSet<T>();
		Collections.addAll(result, list);
		return result;
	}

	public static <T> Collection<T> makeCollection(final Iterator<T> i) {
		final List<T> list = new LinkedList<T>();
		while (i.hasNext()) {
			list.add(i.next());
		}
		return list;
	}

	/**
	 * Construct a string by toString()ing each item in the collection with
	 * inBetween between each item.
	 */
	public static String join(final Collection<?> items, final String inBetween) {
		final StringBuilder builder = new StringBuilder();
		for (final Object item : items) {
			if (builder.length() > 0)
				builder.append(inBetween);
			builder.append(item);
		}
		return builder.toString();
	}

	public static <T> T getSoleElement(final Collection<T> items) {
		if (items.size() != 1)
			throw new IllegalArgumentException(String.format(
					"Expected a single element in %s, but found %s.", items,
					items.size()));
		return items.iterator().next();
	}

	/** Simple multi-map for convenience of storing collections in map values. */
	public static class MultiMap<K, V> extends HashMap<K, Collection<V>> {
		public void append(final K k, final V v) {
			this.initializeKeyIfUninitialized(k);
			this.get(k).add(v);
		}

		public void appendAll(final K k, final Collection<? extends V> v) {
			this.initializeKeyIfUninitialized(k);
			this.get(k).addAll(v);
		}

		private void initializeKeyIfUninitialized(final K k) {
			if (!this.containsKey(k))
				this.put(k, new LinkedList<V>());
		}
	}

	/**
	 * Partitions a collection into groups based on a characteristics of that
	 * group. Partitions are embodied in a map, whose keys are the value of that
	 * characteristic, and the values are the partition of elements whose
	 * characteristic evaluate to that key.
	 */
	public static <K, V> Map<K, Collection<V>> partition(
			final Collection<V> collection, final Partitioner<V, K> p) {
		final MultiMap<K, V> partitionToValues = new MultiMap<K, V>();
		for (final V entry : collection) {
			partitionToValues.append(p.getPartition(entry), entry);
		}
		return partitionToValues;
	}

	public static abstract class Partitioner<V, K> {
		public abstract K getPartition(final V v);
	}

	/**
	 * A defaulting map, which returns a default value when a value that does
	 * not exist in the map is looked up.
	 *
	 * This map supports two modes: injecting-on-default, and not
	 * injecting-on-default. When injecting on default, when a lookup is
	 * performed and a default value is returned, the default value is injected
	 * at that key, so that it now lives in the underlying map. Without this
	 * mode, the value is simply returned and the underlying map is unaffected.
	 *
	 * Note: When using injecting-on-default mode, and performing a lookup with
	 * a non-key type (the get method accepts any object), a class cast
	 * exception will be thrown because a non-key type cannot be added to the
	 * map.
	 * 
	 * @param <K>
	 * @param <V>
	 */
	public static class DefaultingMap<K, V> extends HashMap<K, V> {
		final Factory<V, K> defaultGenerator;
		final boolean injectValueOnDefault;

		/**
		 * Creates a defaulting map which defaults to the provided value and
		 * with injecting-on-default disabled.
		 */
		public DefaultingMap(final V defaultValue) {
			this(new Factory<V, K>() {
				public V make(final K k) {
					return defaultValue;
				}
			}, false);
		}

		/**
		 * Creates a defaulting map that generates defaults from the provided
		 * factory. This is useful when the default is non-static, or the
		 * default is mutable, and the client wishes to get a value and mutate
		 * it and persist those changes in the map.
		 */
		public DefaultingMap(final Factory<V, K> defaultGenerator,
				final boolean injectValueOnDefaulting) {
			this.defaultGenerator = defaultGenerator;
			this.injectValueOnDefault = injectValueOnDefaulting;
		}

		@Override
		@SuppressWarnings("unchecked")
		// Expect that the cast is successful; otherwise, client is breaking
		// contract.
		public V get(final Object key) {
			if (!this.containsKey(key)) {
				final V val = this.defaultGenerator.make((K) key);
				if (this.injectValueOnDefault) {
					this.put((K) key, val);
				}
				return val;
			} else {
				return super.get(key);
			}
		}

		public interface Factory<V, K> {
			/**
			 * @param k
			 */
			V make(K k);
		}
	}
}
